package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _13_根据后序数组重建搜索二叉树 {

    public static TreeNode generalTreeByPostorder(int[] nums) {

        if (!isSearchTreeByPostorder(nums)) {
            return null;
        }

        return doGeneralTreeByPostorder(nums,0,nums.length - 1);
    }

    public static TreeNode doGeneralTreeByPostorder(int[] nums,int left, int right) {

        if (left == right) {

            return new TreeNode(nums[left]);
        }

        int tmp = nums[right];

        int index = left - 1;

        for (int i = left; i < right; i++) {

            if (tmp > nums[i]) {

                index = i;
            }else {
                break;
            }
        }

        TreeNode node = new TreeNode(tmp);

        if (index >= left) {

            node.left = doGeneralTreeByPostorder(nums,left,index);
        }

        if (index + 1 < right) {

            node.right = doGeneralTreeByPostorder(nums,index+1,right - 1);
        }

        return node;
    }

    public static boolean isSearchTreeByPostorder(int[] nums) {

        if (nums == null || nums.length <= 1) {

            return true;
        }

        return isSearchTree(nums,0,nums.length - 1);
    }

    public static boolean isSearchTree(int[] nums, int left, int right) {

        if (left == right) {

            return true;
        }

        int tmp = nums[right];
        boolean flag = false;
        int index = left - 1;
        for (int i = left; i < right; i++) {

            if (tmp > nums[i]) {

                if (flag) {

                    return false;
                }

                index = i;
            }else {

                flag = true;
            }

        }

        if (index >= left && !isSearchTree(nums,left,index)) {
            return false;
        }

        if (index + 1 < right && !isSearchTree(nums,index+1,right - 1)) {

            return false;
        }

        return true;
    }

    public static void main(String[] args) {

        int[] nums = {0,3,4,6,9,7,5};
        TreeNode treeNode = generalTreeByPostorder(nums);
        System.out.println(treeNode);

    }
}
